#include <iostream>
#include <vector>

int findv(std::vector<int>& list, int left, int right)
{
    if(left >= right)
        return left;
    int flag = list[left];
    int first_max_idx = left+1;
    for(int i = left+1; i <= right; i++)
    {
        if(list[i] >= flag)
            continue;
        else
        {
            std::swap(list[i], list[first_max_idx]);
            first_max_idx += 1;
        }
    }
    std::swap(list[left], list[first_max_idx-1]);
    return first_max_idx-1;
}

void qsort(std::vector<int>& list, int left, int right)
{
    if(left >= right)
        return;
    int v = findv(list, left, right);
    qsort(list, left, v);
    qsort(list, v+1, right);
}

int main()
{
    std::vector<std::vector<int>> list = {
        {},
        {1},
        {1,2},
        {2,1},
        {1,2,3,4},
        {4,3,2,1},
        {4,2,3,1},
        {4,3,1,2,5}
    };

    for(int i = 0; i < list.size(); i++)
    {
        for(auto v : list[i])
            std::cout << v << " ";
        
        qsort(list[i], 0, list[i].size()-1);

        std::cout << " --> ";
        for(auto v : list[i])
            std::cout << v << " ";
        std::cout << std::endl;
    }

    return 0;
}